package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC790 {

    static class Solution {
        /**
         * @param generator: Generating set of rules.
         * @param startSymbol: Start symbol.
         * @param symbolString: Symbol string.
         * @return: Return true if the symbol string can be generated, otherwise return false.
         */
        public boolean canBeGenerated(String[] generator, char startSymbol, String symbolString) {
            //图
            Map<Character, Set<String>> g = new HashMap<>();
            for (String s : generator) {
                String[] arr1 = s.split(" -> ");
                String[] arr = s.split(" -> ");
                char key = arr[0].charAt(0);
                String v = arr[1];
                if(!g.containsKey(key))
                    g.put(key,new HashSet<>());

                g.get(key).add(v);
            }

            return dfs(""+startSymbol,symbolString,g);
        }

        //图的深度优先遍历
        public boolean dfs(String cur,String end,Map<Character,Set<String>> g){
            if(cur.equals(end)) return true;
            if(cur.length() > end.length() ) return false;
            List<String> nexts = getNexts(cur,g); //获得邻居节点
            for (String next : nexts) {
                if(dfs(next,end,g)){
                    return true;
                }
            }
            return false;
        }

        public List<String> getNexts(String cur,Map<Character,Set<String>> g){
            List<String> ans = new ArrayList<>();
            for (int i = 0; i < cur.length(); i++) {
                char key = cur.charAt(i);
                if(g.containsKey(key) && g.get(key)!=null){
                    for(String item: g.get(key)){
                        ans.add(cur.substring(0,i)+ item+ cur.substring(i+1));
                    }
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(
                obj.canBeGenerated(new String[]{"S -> abc", "S -> aA", "A -> b", "A -> c"},
                        'S', "ac")); //true
        System.out.println(
                obj. canBeGenerated(new String[]{"S -> abcd", "S -> A", "A -> abc"},
                        'S', "abc")); //true

        System.out.println(
                obj.   canBeGenerated(new String[]{"S -> abc", "S -> aA", "A -> b", "A -> c"},
                        'S', "a")); //false
        System.out.println(obj.canBeGenerated(new String[]{"S -> abc", "S -> aA", "A -> b", "A -> c"},
            'S', "abc"));
    }
}


/*
/*
LintCode-Logo
学习
刷题
题集
群组
内推
VIP
CAT
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
790 · 符号串生成器
算法
中等
通过率
36%
题目
题解6
笔记15
讨论
排名
记录
描述
符号串生成器由两部分组成，开始符号和生成规则集合，
比如对于以下符号串生成器，
开始符合：'S'，生成规则集合：["S -> abc", "S -> aA", "A -> b", "A -> c"]
那么，
符号串 abc 可以被生成，因为 S -> abc。
符号串 ab 可以被生成，因为 S -> aA -> ab。
符号串 ac 可以被生成，因为 S -> aA -> ac。
现在，给你一个符号串生成器，一个符号串，若该符号串可以被生成返回 True，否则返回 False。

我们保证生成规则的左侧为一个大写字母，startSymbol 为一个大写字母，symbolString 为小写字母串。
我们保证 |generator| <= 20, |symbolString| <= 20。
我们保证生成规则集合无左递归，例如不存在这样的["S -> Sb", "S -> A", "A -> Sb"]生成规则集合。
样例
样例 1:
	输入:  generator = ["S -> abc", "S -> aA", "A -> b", "A -> c"], startSymbol = S, symbolString = “ac”
	输出:  true

	解释:
	S -> aA -> ac

样例 2:
	输入: generator = ["S -> abcd", "S -> A", "A -> abc"], startSymbol = S, symbolString = “abc”
	输出:  true

	解释:
	S -> A -> abc

样例 3:
	输入: generator = ["S -> abc", "S -> aA", "A -> b", "A -> c"], startSymbol = S, symbolString = “a”
	输出:  false

	解释:
	无法从S出发得到a

标签
相关题目

121
单词接龙 II
困难

153
数字组合 II
中等

176
图中两个点之间的路线
中等

808
影际网络
中等
推荐课程

系统设计 System Design 2022版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
已开启智能提示
发起考试
30 分 00 秒
910111213141516171819202122232425262728293031323334353637383940414243448745464748495051
        return dfs(String.valueOf(startSymbol),symbolString,map);

    }

    public static boolean dfs(String start,String end,Map<Character,Set<String>> map){
        if(start.equals(end)) return true;
        if(start.length() > end.length()) return false;
        List<String> nexts = getNexts(start,map);
        for (String next : nexts) {
            if(dfs(next,end,map)){

控制台
历史提交
您有309条未读消息，请及时查看

 */


